package or;

import java.util.Arrays;

public class T0047offer {

    public int maxValue(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        for (int[] dpi : dp) {
            Arrays.fill(dpi, 0);
        }
        return dp(grid, dp, grid.length - 1, grid[0].length - 1);
    }


    public int dp(int[][] grid, int[][] dp, int x, int y) {
        if (x < 0 || y < 0) return 0;
        if (dp[x][y] != 0) return dp[x][y];
        int max = Math.max(dp(grid, dp, x - 1, y), dp(grid, dp, x, y - 1));
        max += grid[x][y];
        dp[x][y] = max;
        return max;
    }
}
